package org.example;

import java.util.Random;

public class Sort {
    static class MergeSort {
        // 归并排序：时间复杂度为O(nlogn)是一种采用分治法（Divide and Conquer）的排序算法，它的基本思想是将一个数组分成两个子数组，
        // 分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。
        public static void mergeSort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
            int[] temp = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
        }

        // 递归进行归并排序
        private static void mergeSort(int[] arr, int left, int right, int[] temp) {
            if (left < right) {
                int mid = left + (right - left) / 2;
                // 对左半部分进行排序
                mergeSort(arr, left, mid, temp);
                // 对右半部分进行排序
                mergeSort(arr, mid + 1, right, temp);
                // 合并左右两部分
                merge(arr, left, mid, right, temp);
            }
        }

        // 合并两个有序子数组
        private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
            int i = left; // 左子数组的起始索引
            int j = mid + 1; // 右子数组的起始索引
            int k = left; // 临时数组的起始索引
            // 比较左右子数组的元素，将较小的元素放入临时数组
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            // 将左子数组中剩余的元素复制到临时数组
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            // 将右子数组中剩余的元素复制到临时数组
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            for (i = left; i <= right; i++) {
                arr[i] = temp[i];
            }
        }
    }

    /**
     * 选择排序
     * 稳定性：选择排序是个不稳定排序算法，因为每次都要贾环最小元素和当前元素的位置，这样可能会改变相同元素的位置。
     * 时间复杂度：O(n^2)，最好、最坏、平均时间复杂度均为 O(n²)（无论初始序列是否有序，都需要完成全部比较操作）
     * 空间复杂度：O(1)，选择排序是「原地排序」算法，仅需要 1 个临时变量用于存储交换过程中的元素（或记录最值索引），不需要额外的存储空间。
     */
    static class SelectSort {
        void sort(int[] nums) {
            int n = nums.length;
            // sortedIndex是一个分割线
            // 索引 < sortedIndex的元素都是已排序的
            // 索引 >= sortedIndex的元素都是未排序的
            // 初始化为0，表示整个数组都是未排序的
            int sortedIndex = 0;
            while (sortedIndex < n) {
                // 找到未排序部分[sortedIndex, n]中的最小值
                int minIndex = sortedIndex;
                for (int i = sortedIndex + 1; i < n; i++) {
                    if (nums[i] < nums[minIndex]) {
                        minIndex = i;
                    }
                }
                // 交换最小值和sortedIndex处的元素
                int temp = nums[sortedIndex];
                nums[sortedIndex] = nums[minIndex];
                nums[minIndex] = temp;

                // sortedIndex后移一位
                sortedIndex++;
            }
        }
    }

    /**
     * 冒泡排序
     * 稳定性：稳定排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     */
    // 对选择排序进行第二波优化，获得稳定性的同时避免额外的 for 循环
    // 这个算法有另一个名字，叫做冒泡排序
    static class BubbleSort {
        void sort(int[] nums) {
            int n = nums.length;
            int sortedIndex = 0;
            while (sortedIndex < n) {
                // 寻找nums[sortedIndex]中的最小值
                // 同时将这个最小值逐步移动到nums[sortedIndex]的位置
                for (int i = n - 1; i > sortedIndex; i--) {
                    if (nums[i] < nums[i - 1]) {
                        // swap(nums[i], nums[i-1])
                        int temp = nums[i];
                        nums[i] = nums[i - 1];
                        nums[i - 1] = temp;
                    }
                }
                sortedIndex++;
            }
        }

        // 进一步优化，数组有序时，提前终止算法
        void sort1(int[] nums) {
            int n = nums.length;
            int sortedIndex = 0;
            while (sortedIndex < n) {
                // 加一个bool变量，记录是否进行过交换操作
                boolean swapped = false;
                for (int i = n - 1; i > sortedIndex; i--) {
                    if (nums[i] < nums[i - 1]) {
                        // swap nums[i]和nums[i-1]的位置
                        int temp = nums[i];
                        nums[i] = nums[i - 1];
                        nums[i - 1] = temp;
                    }
                }
                // 如果一次交换操作都没有进行，说明说组已经有序，可以提前终止算法
                if (!swapped) {
                    break;
                }
                sortedIndex++;
            }
        }
    }

    /**
     * 插入排序
     * 稳定排序
     * 插入排序是基于选择排序 的一种优化，将 nums[sortedIndex] 插入到左侧的有序数组中。对于有序度较高的数组，插入排序的效率比较高。
     * 时间复杂度：如果输入的数组是完全逆序的，那么插入排序的效率就会很低，内层 for 循环每次都要对 nums[0..sortedIndex-1] 的所有元素进行交换，算法的总时间复杂度就接近O(n^2)
     * 如果对比插入排序和冒泡排序，插入排序的综合性能应该要高于冒泡排序。
     */
    static class InsertionSort {
        void sort(int[] nums) {
            int n = nums.length;
            int sortedIndex = 0;
            while (sortedIndex < n) {
                // 在未排序的部分中找到最小值nums[minIndex]
                int minIndex = sortedIndex;
                for (int i = sortedIndex + 1; i < n; i++) {
                    if (nums[i] < nums[i - 1]) {
                        minIndex = i;
                    }
                }

                // 交换最小值和 sortedIndex 处的元素
                // int tmp = nums[sortedIndex];
                // nums[sortedIndex] = nums[minIndex];
                // nums[minIndex] = tmp;

                // 优化：将nums[minIndex]插入到nums[sortedIndex]的位置
                // 将nums[sortedIndex..minIndex]的元素整体向后移动一位
                int minVal = nums[minIndex];
                // 数组搬移数组的操作
                for (int i = minIndex; i > sortedIndex; i--) {
                    nums[i] = nums[i - 1];
                }
                nums[sortedIndex] = minVal;

                sortedIndex++;
            }
        }
    }

    /**
     * 希尔排序
     * 不稳定排序
     * 时间复杂度：O(n^2)(插入排序 分析过，插入排序对于有序度较高的数组效率很高，直逼 O(n)，但对于有序度低（元素分布较随机）的数组就只有 O(n^2)了)
     */
    static class ShellSort {
        // 希尔排序，对 h 有序数组进行插入排序
        // 逐渐缩小 h，最后 h=1 时，完成整个数组的排序(这里计算h的公式，决定了这个希尔排序是否高效)
        void sort(int[] nums) {
            int n = nums.length;
            // 我们这里使用的生成函数是2^(k-1)
            // 即h = 1,2,4,8,16
            int h = 1;
            while (h < n / 2) {
                h = 2 * h;
            }
            // 改动一，把插入排序的主要逻辑套在h的while循环中
            while (h >= 1) {
                // 改动二：sortedIndex初始化为h，而不是1
                int sortedIndex = h;
                while (sortedIndex < n) {
                    // 改动三：把比较和交换元素的步长设置为h，而不是相邻元素
                    for (int i = sortedIndex; i >= h; i -= h) {
                        if (nums[i] < nums[i - h]) {
                            // swap(nums[i], nums[i-h])
                            int temp = nums[i];
                            nums[i] = nums[i - h];
                            nums[i - h] = temp;
                        } else {
                            break;
                        }
                    }
                    sortedIndex++;
                }
                // 按照递增函数的规则，缩小h
                h /= 2;
            }
        }
    }

    /**
     * 快速排序
     * 思路：先把一个元素放到正确的位置（排好序），然后将这个元素左右两边剩下的元素利用递归分别排好序，最终整个数组就排好序了。
     * 不稳定排序
     * 时间复杂度：O(log n)
     */
    static class QuickSort {
        public static void sort(int[] nums) {
            // 为了避免出现耗时的极端情况，先随机打乱
            shuffle(nums);
            // 排序整个数组（原地修改）
            sort(nums, 0, nums.length - 1);
        }

        // 洗牌算法，将输入的数组随机打乱
        private static void shuffle(int[] nums) {
            Random rand = new Random();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                // 生成[i, n-1]的随机数
                int r = i + rand.nextInt(n - i);
                swap(nums, i, r);
            }
        }

        private static void sort(int[] nums, int lo, int hi) {
            if (lo >= hi) {
                return;
            }
            // 对nums[lo..hi]进行切分
            // 使得nums[lo..p-1] <= nums[p] < nums[p+1..hi]
            int p = partition(nums, lo, hi);
            // 递归排序左半部分
            sort(nums, lo, p - 1);
            // 递归排序右半部分
            sort(nums, p + 1, hi);
        }

        /**
         * 对nums[lo..hi]进行切分
         * 分区操作：调用partition方法，将[lo, hi]划分为两部分，
         * 返回基准元素的最终位置p（此时nums[p]左边的元素都<= nums[p]，右边的元素都> nums[p]）。
         * 分步解析：
         * 选择基准：以区间最左侧元素nums[lo]作为pivot（基准）。
         * 初始化指针：i从lo+1开始（跳过 pivot），j从hi开始，两者分别向中间移动。
         * 移动指针 i：i向右移动，直到找到第一个> pivot的元素（此时[lo, i)内的元素都<= pivot）。
         * 移动指针 j：j向左移动，直到找到第一个<= pivot的元素（此时(j, hi]内的元素都> pivot）。
         * 交换元素：如果i < j，说明这两个元素位置放反了（小的在右，大的在左），交换它们，确保规则成立。
         * 终止循环：当i >= j时，所有元素已处理完毕，此时j的位置就是pivot的最终位置（因为j左边都<= pivot，右边都> pivot）。
         * 放置 pivot：交换lo（pivot 初始位置）和j，让 pivot 归位，返回j作为切分点。
         *
         * @param nums
         * @param lo
         * @param hi
         * @return
         */
        private static int partition(int[] nums, int lo, int hi) {
            // 选择最左边的元素作为基准（pivot）
            int pivot = nums[lo];
            // 关于区间的边界控制需格外小心，稍后不慎就会出错
            // 我这里i,j定义为开区间，同时定义：
            // [lo, i) <= pivot；(j, hi] > pivot
            // 之后都要正确维护这个边界区间的定义
            int i = lo + 1;
            int j = hi;
            // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
            while (i <= j) {
                // 移动i：找到第一个 > pivot的元素（停在i位置）
                while (i < hi && nums[i] <= pivot) {
                    i++;
                    // 此 while 结束时恰好 nums[i] > pivot
                }
                // 移动j：找到第一个 <= pivot的元素（停在j位置）
                while (j > lo && nums[j] > pivot) {
                    j--;
                    // 此 while 结束时恰好 nums[j] <= pivot
                }
                if (i >= j) {
                    break;
                }
                // 如果i >= j，说明已无需要交换的元素，退出循环
                // 此时 [lo, i) <= pivot && (j, hi] > pivot
                // 交换 nums[j] 和 nums[i]
                swap(nums, i, j);
                // 此时 [lo, i] <= pivot && [j, hi] > pivot
            }
            // 最后将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
            swap(nums, lo, j);
            // 返回pivot的位置j
            return j;
        }

        // 原地交换数组中的两个元素
        private static void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        public static void main(String[] args) {
            int[] nums = new int[]{3, 1, 7, 5, 9, 2, 8, 4, 1, 6, 5};
            QuickSort.sort(nums);
        }
    }
    // 归并排序
    // 思路：把数组切成两半，先把这两半子数组分别排好序，然后再合并这两个有序数组，整个数组就排好序了。
    // 稳定性：稳定排序
    // 时间复杂度：O(nlogn)

    static class MergeSort1 {
        // 用于辅助合并有序数组
        private static int[] temp;

        public static void sort(int[] nums) {
            // 先给辅助数组开启内存空间
            temp = new int[nums.length];
            // 排序整个数组（原地修改）
            sort(nums, 0, nums.length - 1);
        }

        // 定义：将子数组nums[lo..hi]进行排序
        private static void sort(int[] nums, int lo, int hi) {
            if (lo == hi) {
                // 单个元素不用排序
                return;
            }
            // 这样写是为了防止溢出，效果等同于（hi+lo）/2
            int mid = lo + (hi - lo) / 2;
            // 先对左半部分数组nums[lo..mid]排序
            sort(nums, lo, mid);
            // 再对右半部分数组nums[mid+1..hi]排序
            sort(nums, mid+1, hi);
            // 将两部分有序数组合并一个有序数组
            merge(nums, lo, mid, hi);
        }

        // 将nums[lo..mid]和nums[mid+1..hi]这两个有序数组合并成一个有序数组
        private static void merge(int[] nums, int lo, int mid, int hi){
            // 先把nums[lo..hi]复制到辅助数组中
            // 以便合并后的结果能够直接存入nums
            for(int i = lo; i <= hi; i++){
                temp[i] = nums[i];
            }
            // 数组双指针技巧，合并两个有序数组
            int i = lo;
            int j = mid + 1;
            for(int p = lo; p <= hi; p++){
                if (i == mid+1){
                    // 情况1：左半子数组已全部处理完（i走到了左半的末尾）
                    nums[p] = temp[j++]; // 直接取右半子数组的下一个元素
                }else if (j == hi + 1){
                    // 情况2：右半子数组已全部处理完（j走到了右半的末尾）
                    nums[p] = temp[i++]; // 直接取左半子数组的下一个元素
                }else if (temp[i] > temp[j]){
                    // 情况3：两边都没处理完，且右半当前元素更小
                    nums[p] = temp[j++]; // 取右半的元素，j往后移一位
                }else{
                    // 情况4：两边都没处理完，且左半当前元素更小（或相等）
                    nums[p] = temp[i++]; // 取左半的元素，i往后移一位
                }
            }
        }
    }
}
